from typing import List

# 动态规划
class Solution:
	# 最大子序列
	def maxSubArray(self, nums: List[int]) -> int:
		cur_ = nums[0]
		sum_ = nums[0]
		for n in nums[1:]:
			cur_ = n + cur_ if cur_ > 0 else n
			sum_ = max(sum_, cur_)
		print(sum_)

	# 股票最大利润
	def maxProfit(self, prices: List[int]) -> int:
		min_ = prices[0]
		max_ = 0
		for n in prices[1:]:
			min_ = min_ if min_ < n else n
			max_ = max(n - min_, max_)
		print(max_)

if __name__ == '__main__':
	s = Solution()
	s.maxSubArray([-2,1,-3,4,-1,2,1,-5,4])
	s.maxProfit([7,6,4,3,1])